package array;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 target 。
 * 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
 * 由于答案可能很大，请将结果对 109 + 7 取余后返回。
 * <p>
 * 示例 1：
 * 输入：nums = [3,5,6,7], target = 9
 * 输出：4
 * 解释：有 4 个子序列满足该条件。
 * [3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
 * [3,5] -> (3 + 5 <= 9)
 * [3,5,6] -> (3 + 6 <= 9)
 * [3,6] -> (3 + 6 <= 9)
 * <p>
 * 示例 2：
 * 输入：nums = [3,3,6,8], target = 10
 * 输出：6
 * 解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
 * [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
 * <p>
 * 示例 3：
 * 输入：nums = [2,3,3,4,6,7], target = 12
 * 输出：61
 * 解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
 * 有效序列总数为（63 - 2 = 61）
 *
 * @author Jisheng Huang
 * @version 20250507
 */
public class NumSubSeq_1498 {
    /**
     * 用双指针会不会更好一点？
     * 排序之后，当左值加上右值大于target时，说明右值不可能在满足题目条件的序列中，所以可以不用考虑了，右指针直接左移就好了
     *
     * @param nums   the given number
     * @param target the target number
     * @return number of combinations
     */
    public static int numSubSeq(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int mod = 1000000007;
        int[] tmp = new int[n];
        tmp[0] = 1;

        for (int i = 1; i < n; ++i) {
            tmp[i] = (tmp[i - 1] << 1) % mod;
        }

        int res = 0;
        int l = 0;
        int r = nums.length - 1;

        while (l <= r) {
            if (nums[l] + nums[r] > target) {
                --r;
            } else {
                res = (res + tmp[r - l]) % mod;
                ++l;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {3, 5, 6, 7};
        int target = 9;

        System.out.println(numSubSeq(nums, target));

        nums = new int[]{3, 3, 6, 8};
        target = 10;

        System.out.println(numSubSeq(nums, target));

        nums = new int[]{2, 3, 3, 4, 6, 7};
        target = 12;

        System.out.println(numSubSeq(nums, target));
    }
}
